package leetcode101_xqzhao

// TODO 在排序数组中查找元素的第一个和最后一个位置 【-】 二分查找

func searchRange(nums []int, target int) []int {
	n := len(nums)

	left, right := findLeft(nums, target, n), findRight(nums, target, n)
	return []int{left, right}
}

// 寻找左边界
func findLeft(nums []int, target int, n int) int {
	left, right := 0, n-1
	for left <= right {
		mid := (left + right) / 2
		if (nums[mid] == target && mid == 0) || (nums[mid] == target && nums[mid-1] != target) {
			return mid
		}
		if nums[mid] >= target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}

// 寻找右边界
func findRight(nums []int, target int, n int) int {
	left, right := 0, n-1
	for left <= right {
		mid := (left + right) / 2
		if (nums[mid] == target && mid == n-1) || (nums[mid] == target && nums[mid+1] != target) {
			return mid
		}
		if nums[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}
